#include "stdafx.h"
#include "Clique.h"

Clique::Clique(const Graph& g) : G(g)
{
	maxS = 0;
}

//check Search way and return independent vertesis 
void Clique::findIndependentSet(Graph& gr)
{
	mainExpand();
	cout << "Searching is done. Wait For result. \n";
	property_map<Graph, vertex_name_t>::type nameM = get(vertex_name, gr);
	cout << "\n Max independent set of given graph: \n";
	for(Indset::iterator it = maxQ.begin(); it != maxQ.end(); it++)
	{
		cout << (*it) << " ";
		nameM[*it] = "in independant set";
	}
	cout << "\n";
} 

void Clique::mainExpand()
{
	VIter vi, vi_end;
	Indset v;

	property_map<Graph, vertex_index_t>::type index = get(vertex_index,G);
	for(tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi)
	{
		v.insert(index[*vi]);
	}
	//main part of algorithm
	expand(v, v);
}

void Clique::expand(const Indset& subg, Indset& cand)
{
	if(subg.empty())
	{ 
		size_t s = 0;
		if(maxS < (s = Q.size()))
		{
			maxQ = Q;
			maxS = s;
		}
	}
	else
	{
		Indset u, diff;
		neighbourhood(subg, cand, u);
		diff = cand;
		difference(diff, u);
		while(!diff.empty())
		{
			Indset newSubg,newCand;
			Index q = *(diff.begin());
			Q.insert(q);
			pair<AdjItr,AdjItr> adj = adjacent_vertices(q, G);
			intersection(adj, subg, newSubg);
			intersection(adj, cand, newCand);
			//next step of search;
			expand(newSubg , newCand);
			//q is considered;
			cand.erase(q);
			diff.erase(q);
			Q.erase(q);
		}
	}
}

//return set of neighbourhood verteces of vertex from subg
//which has maximal intersection between 
//its neighbourhood and cand set
void Clique::neighbourhood(const Indset& subg, const Indset& cand, Indset& result)
{
	Indset::size_type maxSize,size;
	maxSize = 0;

	for(Indset::const_iterator i = subg.begin(); i != subg.end(); i++)
	{
		Indset temp;
		intersection(adjacent_vertices(*i, G), cand, temp);
		if(maxSize < (size = temp.size()))
		{
			result.clear();
			detail::neighbors(G, *i, inserter(result, result.begin()));
			maxSize = size;
		}
	}
}

//return intersection of a, b sets
template <typename Set, typename AdjIter>
void Clique::intersection(pair<AdjIter,AdjIter> adj, const Set& a, Set& b)
{
	AdjIter ai,aend;

	Set::const_iterator end = a.end();
	for(tie(ai, aend) = adj; ai != aend; ++ai)
	{
		if(a.find(*ai) != end)
		{
			b.insert(*ai);
		}
	}
}

//return a-b
template <typename Set>
void Clique::difference(Set& a, const Set& b)
{ 
	for(Set::const_iterator i = b.begin(); i != b.end(); i++)
	{
		if(a.find(*i) != a.end())
		{
			a.erase(*i);
		}
	}
}